package com.husk.leetcode;

public class DP {

    public static void main(String[] args){

        int N = 10;//楼层总数

        int dp[] = new int[N+1];//用于保存第N楼的最佳次数
        dp[1] = 1;//一楼只需要1次

        int pos[] = new int[N+1];//pos[10]表示，10层大楼扔玻璃珠的位置
        pos[1] = 1;//只有1层楼只能在1楼扔

        //从2层大楼开始
        for (int i = 2; i <= N; i++) {
            int min = N;//每层大楼的最坏情况的最少次数
            for (int j = 1; j < i; j++) {
                int max = dp[i-j] + 1;
                if (max < j)
                    max = j;
                if (min > max) {
                    min = max;
                    pos[i] = j;//记录投掷楼层
                }
            }
            dp[i] = min;
        }

        System.out.println(dp[N]);


        /*找出每次投掷的楼层*/

        int total = N;//每一次的楼层总数
        int[] cast = new int[dp[N]+1];//每一次投掷的位置

        for (int i = 1; i <= dp[N]; i++) {
            cast[i] = pos[total];
            total -= cast[i];
        }

        for (int i = 1; i <= dp[N]; i++) {
            cast[i] += cast[i-1];
        }


        /*打印结果*/
        for (int i : cast) {
            System.out.print(i + " ");
        }

    }


}
